"use strict";

let Puzzle = {
    inversionNum: function (arr) { 
        let length = arr.length;
        let counter = 0;
        for (let i = 0; i < length; i++){
            if (arr[i] == 0) {
                continue;
            }
            for (let j = i + 1; j < length; j++){
                if (arr[j] == 0) {
                    continue;
                }
                if (arr[i] > arr[j]) {
                    counter++;
                }
            }
        }
        return counter;
    },

    inversionPlusOne: function (arr) { 
        let length = arr.length;
        for (let i = 0; i < length; i++){
            if (arr[i] == 0) {
                continue;
            }
            for (let j = i + 1; j < length; j++){
                if (arr[j] == 0) {
                    continue;
                }
                if (arr[i] < arr[j]) {
                    let temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    return;
                }
            }
        }
    },

    getSpaceLine: function (arr) { 
        let length = arr.length;
        let d = Math.sqrt(length);
        for (let i = 0; i < length; i++){
            if (arr[i] == 0) {
                return Math.floor(i / d);
            }
        }
        return NaN;
    },

    initTarget: function (n) { 
        let length = n * n;
        let target = [];
        for (let i = 1; i < length; i++){
            target.push(i);
        }
        target.push(0);
        return target;
    },

    // 3*3(9-1=8), 5*5(25-1=24)
    _puzzleOddNum: function(n) { 
        let length = n * n;
        // target
        let target = this.initTarget(n);
        // puzzle
        let nums = target.slice();
        let puzzle = [];
        for (let i = 0; i < length; i++){
            let nowLength = nums.length;
            let idx = Math.floor(Math.random() * nowLength);
            puzzle.push(nums[idx]);
            nums.splice(idx, 1);
        }
        // judge
        let i1 = this.inversionNum(target);
        let i2 = this.inversionNum(puzzle);
        let isOk = i1 % 2 == i2 % 2;
        if (!isOk) {
            this.inversionPlusOne(puzzle);
        }
        i2 = this.inversionNum(puzzle);
        // produce
        isOk = i1 % 2 == i2 % 2;
        if (isOk) {
            console.log("target:", target.toString(), "inversionNum:", i1);
            console.log("puzzle:", puzzle.toString(), "inversionNum:", i2);
            console.log("ok");
            return [target, puzzle];
        }
        else {
            console.log("bug");
            return null;
        }
    },

    // 4*4(16-1=15), 6*6(36-1=35)
    _puzzleEvenNum: function (n) { 
        let length = n * n;
        // target
        let target = this.initTarget(n);
        // puzzle
        let nums = target.slice();
        let puzzle = [];
        for (let i = 0; i < length; i++){
            let nowLength = nums.length;
            let idx = Math.floor(Math.random() * nowLength);
            puzzle.push(nums[idx]);
            nums.splice(idx, 1);
        }
        // judge
        let i1 = this.inversionNum(target);
        let l1 = this.getSpaceLine(target);
        let i2 = this.inversionNum(puzzle);
        let l2 = this.getSpaceLine(puzzle);
        let l12 = Math.abs(l1 - l2);
        if (i1 % 2 == i2 % 2) {
            // 两个状态的逆序奇偶性相同且空格距离为偶数
            if (l12 % 2 != 0) {
                this.inversionPlusOne(puzzle);
            }
        } else {
            // 两个状态的逆序奇偶性不同且空格距离为奇数
            if (l12 % 2 != 1) {
                this.inversionPlusOne(puzzle);
            }
        }
        i2 = this.inversionNum(puzzle);
        l2 = this.getSpaceLine(puzzle);
        l12 = Math.abs(l1 - l2);
        // produce
        let isOk = (i1 % 2 == i2 % 2 && l12 % 2 == 0) || (i1 % 2 != i2 % 2 && l12 % 2 == 1);
        if (isOk) {
            console.log("target:", target.toString(), "inversionNum:", i1);
            console.log("puzzle:", puzzle.toString(), "inversionNum:", i2, l12);
            console.log("ok");
            return [target, puzzle];
        }
        else {
            console.log("bug");
            return null;
        }
    },

    puzzleCreate: function (n) {
        if (n % 2 == 0) {
            return this._puzzleEvenNum(n);
        } else {
            return this._puzzleOddNum(n);
        }
    }
};

function copyArr(arr, b, n) {
    let copy_arr = [];
    b = b || 0;
    n = n === undefined ? arr.length : n;
    for (let i = b; i < n; i++){
        copy_arr.push(arr[i]);
    }
    return copy_arr;
}

class MNode { 
    constructor(m, f, deep) {
        this.m = m;
        this.lh = Math.sqrt(this.m.length);
        this.f = f;
        this.deep = deep;
        this.parent = null;

        //this.mstr = this.m.toString();
        for (let i = 0; i < this.m.length; i++){
            if (this.m[i] == 0) {
                this.oi = i;
                this.orow = Math.floor(i / this.lh);
                this.oline = i % this.lh;
                break;
            }
        }
    }
    isEqual(m) {
        //return this.mstr == m.toString();
        for (let i = 0; i < this.m.length; i++) { 
            if (this.m[i] != m[i]) {
                return false;
            }
        }
        return true;
    }
    getZeroIdsRowLine() {
        return [this.oi, this.orow, this.oline];
        /*
        for (let i = 0; i < this.m.length; i++){
            if (this.m[i] == 0) {
                let row = Math.floor(i / this.lh);
                let line = i % this.lh;
                return [i, row, line];
            }
        }
        return null;
        */
    }
};
var isCostTime = 0;
var plusCostTime = 0;
class MAStar { 
    constructor(target) { 
        this.target = target;
        this.mapLH = Math.sqrt(this.target.length);
        this.open = [];
        this.close = [];
    }
    isInOC(m) {
        var t1 = new Date().getTime();
        for (let i = 0; i < this.open.length; i++){
            if (this.open[i].isEqual(m)) {
                return true;
            }
        }
        for (let i = 0; i < this.close.length; i++){
            if (this.close[i].isEqual(m)) {
                return true;
            }
        }
        var t2 = new Date().getTime();
        isCostTime += t2 - t1;
        return false;
    }
    plusToOpen(m, p, t) {
        var t1 = new Date().getTime();
        //if (p.deep > 30) return;
        let h = 0;
        for (let i = 0; i < m.length; i++){
            //if (m[i] == 0) continue;
            let row = Math.floor(i / this.mapLH);
            let line = i % this.mapLH;  
            for (let j = 0; i < this.target.length; j++){
                if (this.target[j] == m[i]) {
                    let r = Math.floor(j / this.mapLH);
                    let l = j % this.mapLH;  
                    h += Math.abs(r - row) + Math.abs(l - line);
                    break;
                }
            }
        }    
        let g = p.deep + t;
        let f = g + h;
        let node = new MNode(m, f, p.deep + 1);
        node.parent = p;
        for (let i = 0; i < this.open.length; i++){
            if (node.f < this.open[i].f) {
                this.open.splice(i, 0, node);
                var t2 = new Date().getTime();
                plusCostTime += t2 - t1;
                return;
            }
        }
        this.open.push(node);
        var t2 = new Date().getTime();
        plusCostTime += t2 - t1;
    }
    
    getZeroIdsRowLine(m) {
        for (let i = 0; i < m.length; i++){
            if (m[i] == 0) {
                let row = Math.floor(i / this.mapLH);
                let line = i % this.mapLH;
                return [i, row, line];
            }
        }
        return null;
    }
    optMap(m, opt) {
        let temp = copyArr(m);
        if (opt == 0) return temp;

        let [oi, row, line] = this.getZeroIdsRowLine(temp);
        if (opt == 't' && row - 1 >= 0) {
            let idx = (row - 1) * this.mapLH + line;
            temp[oi] = temp[idx];
            temp[idx] = 0;            
        }else if (opt == 'b' && row + 1 < this.mapLH) {
            let idx = (row + 1) * this.mapLH + line;
            temp[oi] = temp[idx];
            temp[idx] = 0;
        }else if (opt == 'l' && line - 1 >= 0) {
            let idx = row * this.mapLH + line - 1;
            temp[oi] = temp[idx];
            temp[idx] = 0;
        }else if (opt == 'r' && line + 1 < this.mapLH) {
            let idx = row * this.mapLH + line + 1;
            temp[oi] = temp[idx];
            temp[idx] = 0;
        } else {
            temp = null;
        }
        return temp;
    }
};


let mapLH = 3;
let [end, start] = Puzzle.puzzleCreate(mapLH);
console.log("-------------------------");

let mAStar = new MAStar(end);
let p = new MNode(mAStar.optMap(start, 0, 0), 0, 0);
mAStar.open.push(p);
let steps = 0;
while (true) {
    if (mAStar.open.length == 0) {
        p = null;
        break;
    }
    p = mAStar.open[0];
    if (p.isEqual(end)) {
        break;
    }
    steps++;
    console.log("==============", p.m.toString(), steps);
    mAStar.open.splice(0, 1);
    mAStar.close.push(p);
    let [oi, row, line] = p.getZeroIdsRowLine();
    // top
    if (row - 1 >= 0) {
        let newMap = mAStar.optMap(p.m,'t');
        if (newMap && !mAStar.isInOC(newMap)) {
            let t = 1;
            mAStar.plusToOpen(newMap, p, t);
        }
    }
    // bot
    if (row + 1 < mapLH) {
        let newMap = mAStar.optMap(p.m, 'b');
        if (newMap && !mAStar.isInOC(newMap)) {
            let t = 1;
            mAStar.plusToOpen(newMap, p, t);
        }
    }
    // left
    if (line - 1 >= 0) {
        let newMap = mAStar.optMap(p.m, 'l');
        if (newMap && !mAStar.isInOC(newMap)) {
            let t = 1;
            mAStar.plusToOpen(newMap, p, t);
        }
    }
    // right
    if (line + 1 < mapLH) {
        let newMap = mAStar.optMap(p.m, 'r');
        if (newMap && !mAStar.isInOC(newMap)) {
            let t = 1;
            mAStar.plusToOpen(newMap, p, t);
        }
    }
}
console.log(start);
if (p) {
    console.log("------------------");
    let counter = 0;
    while (p) {
        counter++;
        console.log(p.m, p.f, p.deep);
        p = p.parent;
    }
    console.log("ok", counter);
}
else {
    console.log("no way");
}
console.log("isCost:", isCostTime, " plusCost", plusCostTime);